home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / program / swagd_f.zip / EGAVGA.SWG / 0172_Raycasting (Re: Doom) Example.pas < prev    next >
Pascal/Delphi Source File  |  1995-03-03  |  14KB  |  506 lines

  1. (*
  2.  
  3. > Can anyone recomend any books/source/reference/people that would be
  4. > necessary to read/talk to to learn how to do 3 dimensional graphics for
  5. > 1st person game programming similar to the Wolfenstein/Doom/Flight
  6. > simulator type games.
  7.  
  8.   If  you  can read "C", you should look out for ACK3D (a "3D" shareware
  9.   graphic  engine)  which  comes  with  some sources. Note however, that
  10.   neither  ACK3D nor Wolfenstein or Doom are true 3D games: They all use
  11.   a clever technique called "raycasting".
  12.  
  13.   The  underlying  idea  of raycasting is quite simple: use a 2D program
  14.   and  just  paste in a 3rd dimension, only for the screen display. Just
  15.   take  a  2nd  look  at  DOOM  at you'll notice that there is no single
  16.   location  in the map where you may have two different height-positions
  17.   throughout  the  game.  Or more mathematically: There is no coordinate
  18.   (x,y) in the plane for which there are more than one z-coordinate. The
  19.   basic  map  of  such games is a normal 2D map: the player moves within
  20.   this  plane  (which  is divided by a grid into basic "blocks") and his
  21.   view  will  be computed for each animation frame. For example, say his
  22.   angle  of view is 60 degrees. Then from his actual position, imaginary
  23.   rays  will  be  sent out from -30..+30 degrees through the 2D (!) map.
  24.   Each  ray  is  traced until it hits a block of the grid. The according
  25.   object  will  then  be drawn to the screen at the proper position; the
  26.   length  of  the  ray  from the player's position to the hit-point is a
  27.   measurement  how  far  the object is from the viewer and thus, how big
  28.   (and bright) the object should be drawn.
  29.   As the player only moves within the (x,y) plane, there is no change of
  30.   information  in  the  z-coordinate. Therefore, for each screen column,
  31.   there is only one single computation necessary! (Even small changes in
  32.   the z-coordinate could be simulated easily by shifting the column data
  33.   a  bit). The profits are dramatic: for a screen resolution of 320x200,
  34.   you  only  have  320  computations  (instead  of  64000)  --that's  an
  35.   improvement of 99.5%!
  36.   The problem with this method is the exact detection where the rays hit
  37.   the  grid blocks. Instead of decreasing the mesh size of the grid, one
  38.   may  think  that  the  original  blocks  consist of a second "subgrid"
  39.   (ACK3D  uses  a  64x64  subgrid for each block). If you start counting
  40.   blocks  row-wise,  starting  with zero, then you can compute the block
  41.   number  and  the  relative  coordinates  (rx1,ry1)  of  a point P with
  42.   absolute corrdinates (x1,y1) by
  43.  
  44.   b = (y1 DIV 64)*gridwidth_in_blocks + (x1 DIV 64)
  45.   rx1 = x1 MOD 64
  46.   ry1 = y1 MOD 64
  47.  
  48.   See the profits of powers of two for the subgrid size here?:
  49.   b = (y1 SHR 6)*gridwidth_in_blocks + (x1 AND 63)
  50.   rx1 = x1 AND 63
  51.   ry1 = y1 AND 63
  52.  
  53.   Computing the collision points rays <-> blocks is pure trigonometry:
  54.   Given are the position of the player P = (x1,y1) and his viewing angle
  55.   alpha  (measured  from the x-axis, for example). If he is looking with
  56.   angle of 20 degrees, one would have to compute all rays from 20-30=-10
  57.   degrees  up  to  20+30=50  degrees.  If your screen has a width of 320
  58.   columns, then a simple algorithm would look something like this:
  59.  
  60. column:=0
  61. FOR beta:=alpha-30 TO alpha+30 STEP 60/320
  62.   cast ray from P=(x1,y1) with angle beta
  63.   IF ray hits nontransparent block b
  64.     THEN draw block columns which we hit
  65.          at screen position "column";
  66.          compute distance to hit location and
  67.          darken graphic accordingly
  68.   ELSEIF ray leaves the plane edge
  69.     THEN draw complete column black
  70.   ELSE {ray runs through empty/transparent block}
  71.     trace ray further
  72.   INC(column)
  73. ENDFOR
  74.  
  75.   As  we  do  have a fixed size of the game area, we do know the maximum
  76.   length  of  a  ray  in before. If the ray's length is bigger than this
  77.   maximum, you may stop tracing the ray any further. Using a bit college
  78.   math  trigometry,  one  can  optimize this even further to compute the
  79.   last   point   Q   =  (x2,y2)  on  the  ray  which  must  be  checked:
  80.   x2:=x1+cos(beta)*diag;    y2:=y1+sin(beta)*diag;    (diag:=length   of
  81.   diagonal of the (x,y) plane).
  82.  
  83.   Now  just  use  some  standard line-algorithm like Brensenham's on the
  84.   line  between  P and Q and check the points if they hit a block and if
  85.   so,  where.  Note  that  you don't have to check every point, but only
  86.   those which lie on the grid edges!
  87.  
  88.  
  89. > Can this type of program be created with Pascal or are they Assembler/C
  90. > only areas?
  91.   I  once  saw  a  small piece of (buggy) PASCAL code, but didn't try to
  92.   debug it more than necessary; however, it should suffice for a start:
  93. *)
  94.  
  95. PROGRAM RayCast2;
  96. USES DOS, CRT;
  97. TYPE
  98.  { Map : 10 * 10 squares - 1 square consists of 64 * 64 units !! }
  99.      TMap = ARRAY[1..10] OF ARRAY[1..10] OF BYTE;
  100.      TPlayer= OBJECT
  101.                 x            ,
  102.                 y            : SHORTINT;
  103.                 ViewPoint  : INTEGER;
  104.                 MapX       ,
  105.                 Mapy       : SHORTINT;
  106.                 PROCEDURE Init;
  107.               END;
  108.       HeightTab = ARRAY[0..90] OF BYTE;
  109.       WallBmp= ARRAY[0..63] OF BYTE;
  110.  
  111. CONST Up   = 1;
  112.       Down = 2;
  113.       Right =3;
  114.       Left  =4;
  115.  
  116. VAR Map : TMap;
  117.     P     : TPlayer;
  118.     ch    : CHAR;
  119.     xAtt  ,
  120.     yAtt  : BYTE;
  121.     Angle : REAL;
  122.     Height ,
  123.     Width  : BYTE;
  124.     Distance: INTEGER;
  125.     yDis   ,
  126.     xDis   ,
  127.     Hyp    : REAL;
  128.     DeltaX ,
  129.     DeltaY : REAL;
  130.     DeltaKX,
  131.     DeltaKY: LONGINT;
  132.     WMapX,
  133.     WMapY: INTEGER;
  134.     Column ,
  135.     XColumn,
  136.     YColumn: SHORTINT;
  137.     HeightTabTable : HeightTab;
  138.     Wall        : WallBmp;
  139.     sinus, cosinus:ARRAY[0..359] OF REAL;
  140.     i:INTEGER;
  141.  
  142. PROCEDURE Modus(m:WORD); ASSEMBLER;
  143. ASM
  144.   MOV AX,m
  145.   INT $10
  146. END;
  147.  
  148. PROCEDURE TPlayer.Init;
  149. BEGIN
  150.   MapX:=2; MapY:=2;
  151.   x:=32; y:=32;
  152.   Angle:=0;
  153. END;
  154.  
  155. FUNCTION init:BOOLEAN;
  156. VAR x,y : BYTE;
  157.     HeightTabF : FILE OF HeightTab;
  158. BEGIN
  159.   Modus($13);
  160.   { Erase Map }
  161.   FOR x:=1 TO 10 DO
  162.     FOR y:=1 TO 10 DO
  163.       Map[x,y]:=0;
  164.  
  165.   { Draw a few walls }
  166.   FOR x:=1 TO 10 DO BEGIN
  167.     Map[x,1]:=129;
  168.     Map[x,10]:=129;
  169.   END;
  170.   FOR y:=1 TO 10 DO BEGIN
  171.     Map[1,y]:=129;
  172.     Map[4,y]:=129;
  173.     Map[10,y]:=129;
  174.   END;
  175.   Map[2,3]:=129;
  176.   { Build Character }
  177.   P.Init;
  178.   FOR x:=0 TO 90 DO
  179.     HeightTabTable[x]:=90-x;
  180.  
  181.   { Different Palette }
  182.   { JansPalette; }
  183.   { Init Wall Bitmap }
  184.   FOR x:=0 TO 31 DO
  185.     Wall[x]:=100+x;
  186.   FOR x:=32 TO 63 DO
  187.     Wall[x]:=100-(x-32);
  188. END;
  189.  
  190. PROCEDURE Clear; ASSEMBLER;
  191. ASM
  192.  CLD
  193.  MOV AX,$A000
  194.  MOV ES,AX
  195.  MOV CX,32000
  196.  XOR AX,AX
  197.  REP STOSW
  198. END;
  199.  
  200. PROCEDURE deInit;
  201. BEGIN
  202.   Modus( 3 );
  203. END;
  204.  
  205. PROCEDURE DownProc;  { looking down }
  206. BEGIN
  207.   yDis:=907;
  208.   { Step through each square }
  209.   FOR Height:=P.MapY+1 TO 10 DO BEGIN
  210.     Distance:= 65-P.Y + 64 * (Height-P.MapY-1);
  211.     Hyp    := Distance / cosinus[Round(angle)];
  212.     DeltaX := sinus[Round(angle)] * Hyp;
  213.     IF DeltaX>MaxLongInt THEN DeltaX:=MaxLongInt;
  214.     { Subtract when looking to the right , else add}
  215.     IF xAtt=Right THEN
  216.       DeltaKX:= (P.MapX-1)*64+P.X - Round(DeltaX)
  217.     ELSE
  218.       DeltaKX:= (P.MapX-1)*64+P.X + Round(DeltaX);
  219.  
  220.     WMapX:= DeltaKX DIV 64+1;
  221.     XColumn:= DeltaKX MOD 64;
  222.     WMapY:= Height;
  223.     Hyp:=Abs(Hyp);
  224.     { If out of bounds or wall found }
  225.     IF (WMapX<1) OR (WMapX>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
  226.     BEGIN
  227.       yDis:=Hyp;
  228.       Height:=10;
  229.     END
  230.   END;
  231.   IF (xDis>906) AND (yDis>906) THEN BEGIN
  232.     Distance:=906;
  233.     Column :=0;
  234.   END ELSE
  235.     IF yDis<xDis THEN BEGIN
  236.       Distance:=Round(yDis);
  237.       Column:= xColumn;
  238.     END ELSE BEGIN
  239.       Distance:=Round(xDis);
  240.       Column :=yColumn;
  241.     END;
  242. END;
  243.  
  244. PROCEDURE UpProc;
  245. BEGIN
  246.   yDis:=907;
  247.   FOR Height:=P.MapY-1 DOWNTO 1 DO BEGIN
  248.     Distance:= -P.Y - 64 * (P.MapY-Height-1);
  249.     Hyp    := Distance / cosinus[Round(angle)];
  250.     DeltaX := sinus[Round(angle)] * Hyp;
  251.     DeltaKX:= (P.MapX-1)*64+P.X- Round(DeltaX);
  252.     WMapX:= DeltaKX DIV 64+1;
  253.     XColumn:= DeltaKY MOD 64;
  254.     WMapY:= Height;
  255.     Hyp    :=ABs(Hyp);
  256.     { If out of bounds, or wall struck }
  257.     IF (WMapX<1) OR (WMapX>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
  258. BEGIN      yDis:=Hyp;
  259.       Height:=1;
  260.     END
  261.   END;
  262.   IF (xDis>906) AND (yDis>906) THEN BEGIN
  263.     Distance:=906;
  264.     Column:=0;
  265.   END ELSE
  266.     IF yDis<xDis THEN BEGIN
  267.       Distance:=Round(yDis);
  268.       Column:=xColumn;
  269.     END ELSE BEGIN
  270.       Distance:=Round(xDis);
  271.       Column:=YColumn;
  272.     END;
  273.  
  274. END;
  275.  
  276.  
  277. PROCEDURE RightProc(angle:WORD);
  278. BEGIN
  279.   xDis:=907;
  280.   FOR Width:=P.MapX+1 TO 10 DO BEGIN
  281.     Distance:= 65-P.X + 64 * (Width-P.MapX-1);
  282.     Hyp    := Distance / cosinus[angle];
  283.     DeltaY := sinus[angle] * Hyp;
  284.     IF DeltaY>MaxLongInt THEN DeltaY:=MaxLongInt;
  285.     DeltaKY:= (P.MapY-1)*64 +P.Y -Round(DeltaY);
  286.  
  287.     WMapX:= Width;
  288.     WMapY:= DeltaKY DIV 64 +1;
  289.     YColumn:= DeltaKY MOD 64;
  290.     Hyp    := Abs(Hyp);
  291.  
  292.     { If out of bounds, or wall struck }
  293.     IF (WMapY<1) OR (WMapY>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
  294. BEGIN      Width:=10;
  295.       xDis:=Hyp;
  296.     END;
  297.   END;
  298.   { Now check yRay }
  299.   CASE yAtt OF
  300.     Down : DownProc;
  301.     Up  : UpProc;
  302.   END;
  303. END;
  304.  
  305. PROCEDURE LeftProc(angle:WORD);
  306. BEGIN
  307.   xDis:=907;
  308.   FOR Width:=P.MapX-1 DOWNTO 1 DO BEGIN
  309.     Distance:= -P.X - 64 * (P.MapX-Width-1);
  310.     Hyp    := Distance / cosinus[angle];
  311.     DeltaY := sinus[angle] * Hyp;
  312.     DeltaKY:= (P.MapY-1)*64 + P.Y - Round(DeltaY);
  313.  
  314.     WMapX:= Width;
  315.     WMapY:= DeltaKY DIV 64 +1;
  316.     YColumn:= DeltaKY MOD 64;
  317.     Hyp    := Abs(Hyp);
  318.     { If out of bounds, or wall struck }
  319.     IF (WMapY<1) OR (WMapY>10) OR (Hyp>906) OR (Map[WMapX,WMapY]>128) THEN
  320. BEGIN      Width:=1;
  321.       xDis:=Hyp;
  322.     END;
  323.   END;
  324.   { Now check yRay }
  325.   CASE yAtt OF
  326.     Down : DownProc;
  327.     Up  : UpProc;
  328.   END;
  329. END;
  330.  
  331. PROCEDURE Proc0; { Angle = 0 degrees }
  332. BEGIN
  333.   WMapY:=P.MapY;
  334.   Column:= 0;
  335.   Distance:=907;
  336.   FOR Width:=P.MapX+1 TO 10 DO BEGIN
  337.     WMapX:=Width;
  338.     IF Map[WMapX,WMapY]>128 THEN BEGIN
  339.       Distance:=65-P.x + 64 * (Width-P.MapX-1);
  340.       Width:=10;
  341.       Column:=P.y;
  342.     END;
  343.   END;
  344. END;
  345.  
  346. PROCEDURE Proc18; { Angle = 180 degrees }
  347. BEGIN
  348.   WMapY:=P.MapY;
  349.   Column :=0;
  350.   Distance:=907;
  351.   FOR Width:=P.MapX-1 DOWNTO 1 DO BEGIN
  352.     WMapX:=Width;
  353.     IF Map[WMapX,WMapY]>128 THEN BEGIN
  354.       Distance:=Abs( -P.X - 64 * (P.MapX-Width-1) );
  355.       Width:=1;
  356.       Column:=P.Y;
  357.     END;
  358.   END;
  359. END;
  360.  
  361. PROCEDURE Proc27; { Angle = 270 degrees }
  362. BEGIN
  363.   WMapX:=P.MapX;
  364.   Distance:=907;
  365.   Column :=0;
  366.   FOR Height:=P.MapY+1 TO 10 DO BEGIN
  367.     WMapY:=Height;
  368.     IF Map[WMapX,WMapY]>128 THEN BEGIN
  369.       Distance:=65-P.y + 64 * (Height-P.MapY-1);
  370.       Height:=10;
  371.       Column:=P.Y;
  372.     END;
  373.   END;
  374. END;
  375.  
  376. PROCEDURE Proc90; { Angle = 90 degrees }
  377. BEGIN
  378.   WMapX:=P.MapX;
  379.   Column:=0;
  380.   Distance:=907;
  381.   FOR Height:=P.MapX-1 DOWNTO 1 DO BEGIN
  382.     WMapY:=Height;
  383.     IF Map[WMapX,WMapY]>128 THEN BEGIN
  384.       Distance:=Abs( -P.Y - 64 * (P.MapY-Height-1)  );
  385.       Height:=1;
  386.       Column:=p.Y;
  387.     END;
  388.   END;
  389. END;
  390.  
  391. PROCEDURE VLine(x,y1,y2:WORD; c:BYTE); ASSEMBLER;
  392. ASM
  393.  MOV CX,y2
  394.  MOV DI,y1
  395.  SUB CX,DI
  396.  JCXZ @ende
  397.  JG @doit
  398.  NEG CX
  399.  MOV DI,y2
  400. @doit:
  401.  MOV AX,320
  402.  MUL DI
  403.  ADD AX,x
  404.  MOV DI,AX
  405.  CLD
  406.  MOV AL,c
  407.  MOV DX,320
  408. @l1:
  409.  MOV ES:[DI],AL
  410.  ADD DI,DX
  411.  LOOP @l1
  412. @ende:
  413. END;
  414.  
  415. PROCEDURE Draw;
  416. VAR counter: INTEGER;
  417.     intAngle:WORD;
  418. BEGIN
  419.   { 70 degree viewfield (not just 60) }
  420.   angle:=(70*160 / 320) + P.ViewPoint;
  421.   IF angle>=360 THEN angle:=angle-360;
  422.  
  423.   FOR counter:=0 TO 319 DO BEGIN { loop each column }
  424.    intAngle:=Round(angle);
  425.     IF intAngle=90 THEN             { xDirection }
  426.       xAtt:=90
  427.     ELSE
  428.       IF intAngle=270 THEN
  429.         xAtt:=27
  430.       ELSE
  431.         IF (intAngle<90) OR (intAngle>270) THEN
  432.           xAtt:=Right
  433.         ELSE
  434.           xAtt:=Left;
  435.     IF intAngle=180 THEN            { y Direction }
  436.       xAtt:=18
  437.     ELSE
  438.       IF intAngle=0 THEN
  439.         xAtt:=0
  440.       ELSE
  441.         IF intAngle<180 THEN
  442.           yAtt:=Up
  443.         ELSE
  444.           yAtt:=Down;
  445.  
  446.     CASE xAtt OF
  447.       Right : RightProc(intAngle);
  448.       Left  : LeftProc(intAngle);
  449.       0      : Proc0;
  450.       18     : Proc18;
  451.       90     : Proc90;
  452.       27     : Proc27;
  453.     END;
  454.  
  455.     { Draw Line }
  456.     VLine(counter,99,99-HeightTabtable[Distance DIV 10],Wall[Abs(Column)]);
  457.  
  458.     { decrease angle }
  459.     angle:=angle- (70 / 320);
  460.     IF angle<0 THEN angle:=angle+360;
  461.   END; { next column }
  462. END;
  463.  
  464. BEGIN
  465.   FOR i:=0 TO 359 DO
  466.    BEGIN
  467.     cosinus[i]:=cos(i*Pi/180);
  468.     sinus[i]  :=sin(i*Pi/180);
  469.    END;
  470.   ch:=#1;
  471.   IF Init THEN BEGIN
  472.     P.ViewPoint:=90;
  473.     REPEAT   { Loop until ESC pressed }
  474.       Clear;
  475.       Draw;
  476.       ch:=ReadKey;
  477.       CASE ch OF
  478.         'a' : BEGIN  { Left turn }
  479.                 Inc(P.ViewPoint,5);
  480.                 IF P.ViewPoint>359 THEN P.ViewPoint:=P.ViewPoint-360;
  481.               END;
  482.         's' : BEGIN {right turn }
  483.                 Dec(P.ViewPoint,5);
  484.                 IF P.ViewPoint<0 THEN P.ViewPoint:=P.ViewPoint+360;
  485.               END;
  486.         'w' : BEGIN { Move forward }
  487.                 Dec(P.y,2);
  488.                 IF P.y<1 THEN BEGIN
  489.                   Dec(P.MapY);
  490.                   P.y:=64+P.y;
  491.                 END;
  492.               END;
  493.         'y' : BEGIN {Move backward }
  494.                 Inc(P.y,2);
  495.                 IF P.y>64 THEN BEGIN
  496.                   Inc(P.MapY);
  497.                   P.y:=P.y-64;
  498.                 END;
  499.               END;
  500.       END;
  501.  
  502.     UNTIL ch=#27;
  503.     DeInit;
  504.   END;
  505. END.
  506.